package 蓝桥杯算法;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class day34 {
    public static void main(String[] args) {
        int[][]graph={{1,2},{2,1},{1,3},{2,4}};
        List<List<Integer>> adjist=new ArrayList<>();
        for(int i=0;i<graph.length;i++){
            adjist.add(new ArrayList<>());
        }
        //邻接表
        for(int i=0;i<graph.length;i++){
                //创建相应的邻接表
                adjist.get(graph[i][0]-1).add(graph[i][1]-1);
        }
        Boolean[] visited=new Boolean[graph.length];
        for(int i=0;i<graph.length;i++){
            visited[i]=false;
        }
        //进行深搜，如果存在visited为零，则说明无法到达
       bfs(visited,0,adjist);
        for(int i=0;i<graph.length;i++){
            if(!visited[i]){
                System.out.println(-1);
                return;
            }
        }
        System.out.println(1);
    }
    public static void dfs(Boolean[] visited,int key,List<List<Integer>> adjist){//深搜
        if(visited[key]){
            return;
        }
        visited[key]=true;
        List<Integer> nextKey=adjist.get(key);
        //获取每个表对应的邻接表
        for(int next:nextKey){
            dfs(visited,next,adjist);
        }
    }
    public static void bfs(Boolean[] visited,int key,List<List<Integer>> adjist){//广度优先遍历
        Queue<Integer> queue=new LinkedList<>();
        queue.add(key);
        visited[key]=true;
        while(!queue.isEmpty()){
            int cur=queue.poll();
            List<Integer> list=adjist.get(cur);
            for(int curr:list){
                if(!visited[curr]){
                    queue.add(curr);
                    visited[curr]=true;
                }
            }

        }


    }
}


